package com.LeeCode;

import java.util.HashMap;
import java.util.Map;

/**
 * 使数组和能被 P 整除
 */

public class Code1590 {
    public static void main(String[] args) {
        int[] nums = {26, 19, 11, 14, 18, 4, 7, 1, 30, 23, 19, 8, 10, 6, 26, 3};
        int p = 26;
        System.out.println(new Code1590().minSubarray(nums, p));
    }

    public int minSubarray(int[] nums, int p) {
        int n = nums.length;

        // 计算数组总和对p的余数
        int totalRemainder = 0;
        for (int num : nums) {
            totalRemainder = (totalRemainder + num) % p;
        }

        // 如果总和已经能被p整除，不需要删除任何元素
        if (totalRemainder == 0) {
            return 0;
        }

        // 使用HashMap存储前缀和余数及其索引
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1); // 前缀和余数为0的索引为-1

        int prefixSum = 0;
        int minLen = n; // 初始化为数组长度（表示删除整个数组）

        for (int i = 0; i < n; i++) {
            prefixSum = (prefixSum + nums[i]) % p;

            // 我们需要找到子数组，使得：
            // (prefixSum - previousPrefixSum) % p = totalRemainder
            // 即：previousPrefixSum % p = (prefixSum - totalRemainder) % p
            int need = (prefixSum - totalRemainder) % p;
            if (need < 0) {
                need += p; // 处理负数情况
            }

            if (map.containsKey(need)) {
                int len = i - map.get(need);
                minLen = Math.min(minLen, len);
            }

            map.put(prefixSum, i);
        }

        // 如果minLen等于数组长度，说明需要删除整个数组，这是不允许的
        return minLen == n ? -1 : minLen;
    }
}
